#include <iostream>
#include <queue>
#include <utility>

typedef struct BiNode{
    int data;
    BiNode *LChild;
    BiNode *RChild;
}BiNode,*BiTree;

void initTree(BiTree &tree);
void getTree(BiTree &tree);
void ReverseTree(BiTree &tree);
void Level_Order(BiTree &tree);

int main() {
    // the number of the test sets
    int T = 0;
    std::cin >> T;
    for (int i = 0; i < T; i++) {
        BiTree tree = new BiNode;
        initTree(tree);
        getTree(tree);
        ReverseTree(tree);
        Level_Order(tree);
    }
}

// Initialize the tree
void initTree(BiTree &tree) {
    tree->data = 0;
    tree->LChild = 0;
    tree->RChild = 0;
}

// get the tree nodes in level order
void getTree(BiTree &tree) {
    int key = 0;// Use the key to access each data
    std::cin >> key;
    // First get the data of the root
    tree->data = key;
    BiNode* node = tree;
    std::queue<BiNode*> que;
    que.push(node);
    
    // Get each data of the leftchild and rightchild
    // If it is not 0, push into the queue
    // Otherwise, make it point to NULL
    while(!que.empty()) {
        node = que.front();
        node->LChild = new BiNode;
        node->RChild = new BiNode;
        que.pop();

        std::cin >> key;
        if(key != 0){
            que.push(node->LChild);
            node->LChild->data = key;
        }
        else if (key == 0) {
        	node->LChild = NULL;
		}
            
        std::cin >> key;
        if(key != 0){
            que.push(node->RChild);
            node->RChild->data = key;
        }
        else if (key == 0) {
        	node->RChild = NULL;
		}
    }
    std::cin>>key;
    return;
}

// swap the left child and right child of each node
void ReverseTree(BiTree &tree) {
    if (tree != NULL) {
		std::swap(tree->LChild,tree->RChild);
		ReverseTree(tree->LChild);
		ReverseTree(tree->RChild);
	}
}

// Print the tree in level order
void Level_Order(BiTree &tree) {
    std::cout << tree->data << " ";
    BiNode* node = tree;
    std::queue<BiNode*> que;
    que.push(node);
    
    while(!que.empty()) {
        node = que.front();
        que.pop();

        if(node->LChild != 0){
            que.push(node->LChild);
            std::cout << node->LChild->data << " ";
        }
        else if (node->LChild == 0) {
        	std::cout << 0 << " ";
		}
            
        if(node->RChild != 0){
            que.push(node->RChild);
            std::cout << node->RChild->data << " ";
        }
        else if (node->RChild == 0) {
        	std::cout << 0 << " ";
		}
    }
    std::cout << "\n";
    return;
}